1. Field of the Invention
The present invention relates generally to pattern classification systems and, more particularly, to a self-organizing neural network for pattern classification, which is able to vary a response signal by learning to separate and to identify a correct class of the input signal from repeated presentations of an input pattern signal.
2. Description of the Prior Art
Recognition devices, such as character, voice, or target recognition devices, separate input pattern signals into classes. Such recognition devices rely on pattern recognition techniques, such as template matching or structure analytic techniques, which require manual development and input of the information necessary for classifying input pattern signals. These techniques also require manual adjustment for properly separating classes. Such manual intervention decreases the efficiency of the system and creates the possibility of human error being injected into the system.
In order to eliminate the necessity of manual development and input of the requisite information, a pattern classifying technique has been developed which is able to organize itself to classify input pattern signals of a given number of classes without manual assistance. This technique utilizes a neural network. FIG. 1 shows a conventional self-organizing pattern classification system that adopts such a pattern classifying technique. The system uses a learning vector quantization 2 (LVQ2) selector such as shown by Teuvo Kohonen, Gyorgy Barna, and Ronald Chrisley, "Statistical Pattern Recognition with Neural Networks: Benchmarking Studies", Proceedings of IEEE International Conference on Neural Networks, Jul. 24-27, 1988, Vol. 1, pp. 61-68.
In FIG. 1, the classification system includes N input nodes 2, each serving as a buffer for receiving a respective element Si of an input pattern signal S having N elements: S1, S2, . . . , SN, where N and i are positive integers. The classification system also includes M intermediate nodes 3, where M is a positive integer. Each intermediate node 3 receives a copy of the N-dimensional input pattern signal from the N input nodes 2 via signal lines 8 and generates an intermediate output 10. The significance of the intermediate output will be discussed below. Additionally, the system has an LVQ2 selector 4 for receiving the M intermediate output signals 10 from the M intermediate nodes 3 via signal lines 9. The LVQ2 selector 4 receives a teaching signal 6 from an external device and generates a response signal 5 indicating the correct class of input. The selector 4 also generates a learning signal 7 which is sent to the intermediate nodes 3 via signal lines 11.
An example of the input pattern signal S of N elements S1, S2, . . . , SN is a signal resulting from the pre-processing or feature extracting process used in character recognition techniques. This input pattern includes information such as geometric moments and topological features as described by W. E. Weiderman, M. T. Manry and H. C. Yau in "A Comparison of A Nearest Neighbor Classifier and A Neural Network For Numeric Handprint Character Recognition," Proceedings of International Joint Conference on Neural Networks, Jun. 18-22, 1989, Vol. 1, pp. 117-120. The input pattern may also be the product of voice recognition strategies or the product of target recognition strategies. In general, the input pattern may consist of various forms of audio or visual data. Reference is made hereinafter to a character pattern solely for illustrative purposes.
FIG. 2 shows a structure of the i-th intermediate node Ui, which includes N element comparators 12. Each of the element comparators 12 receives a respective element of the input signal S. Each element comparator 12 compares an element Sj of the input pattern S with a corresponding weighting factor vector element Wij and squares the difference between the input element and the corresponding weighting factor vector element. The element comparator 12 transfers the squared difference to the adder 13 via a signal line 15. The adder 13 sums all of the squared differences from the respective element comparators 12 and transmits the summation result to the square root computer 14 via a signal line 16. The square root computer 14 calculates the square root of the summation result and forwards the square root as the output signal Oi of the intermediate node Ui over line 9. As a result of the operations performed by the above-described element, the intermediate output Oi of the i-th intermediate node Ui is given by the following expression: ##EQU1## wherein Sj is the j-th scalar element of an input pattern signal S and Wij is the j-th scalar element of the weighting factor Wi stored in the i-th intermediate node Ui.
The conventional system operates in either a "recognition mode" or a "learning mode." In the recognition mode, an input pattern signal S consisting of N elements S1, S2, . . . , SN is separated into and identified as being within a class. In particular, the system of FIG. 1 receives N elements S1, S2, . . . , SN of an input pattern signal S, determines a class to which the input pattern signal S belongs, and outputs the class in a response signal 5. In the learning mode, the weighting factor vector Wi of an intermediate node Ui is modified to correctly classify the input pattern signal S.
In recognition mode, the response signal 5 corresponds to the class information which has been determined by this system. For example, when the system is requested to classify 26 English capital letters A-Z, it outputs information about each one of the 26 classes A-Z as a response signal 5. This is accomplished by comparing the weighting factors in the intermediate node 3 to the input pattern signal S as described above. That is, the weighting factors for each class serve as a template representation of the characteristics of the letter that the class represents. Each intermediate node 3 has N weighting factors held in its respective element comparators 12 which serve as a template representation of a particular class. The number of intermediate nodes 3 used is greater than the number of classes to be recognized because two or more intermediate nodes represent the distribution of pattern signals for each class. Each node represents a different template for the same class. For example, as shown in FIG. 3a, there are various different representations of letters that are, nevertheless, all directed to the same letter. Thus, all five representations of the letter "A" in FIG. 3a fall in the same class, but each representation of "A" has a separate template encoded in a unique intermediate node.
Another way of highlighting that different intermediate nodes hold templates of the same class is to view each template as a vector. In FIG. 3b, a simplified version of the vectors for the letters A and B is depicted. This figure assumes for illustrative purposes only, that each template is a vector having only 2 scalar elements (X.sub.1, X.sub.2). In FIG. 3b, there are three intermediate nodes Ua1, Ua2, and Ua3, representing the letter "A" and four intermediate nodes Ub1, Ub2, Ub3, and Ub4 representing the letter "B". The output value Oi of the i-th intermediate node Ui given by expression (1) is equivalent to the Euclidian distance in a vector space between an input pattern signal vector S (wherein each element of input is a scalar element of the vector) and a template vector represented by the weighting factors Wij (j=1, 2, . . . , N). Thus, the smaller the output value Oi, the closer (i.e. the less the Euclidian distance) the input pattern signal vector S and the template vector represented by the weighting factors Wij are in the vector space. Based on this concept, the LVQ2 selector 4 selects the intermediate node Ukmin which gives the minimum output value as the closest intermediate node to the input pattern signal S and outputs the class name for the intermediate node Ukmin as a response signal 5. In FIG. 3b, if S is an input pattern signal represented as a point in the vector space, the distances to the points representing the intermediate nodes Ua1-Ua3 and Ub1-Ub4 are Oa1-Oa3 and Ob1-Ob4, respectively. The intermediate node Ua1 gives the minimum distance Oa1. Consequently, the system outputs, as a response signal 5, the class corresponding with the letter "A" as encoded in the weights of the intermediate node Ua1.
In the learning mode, the response signal 5 determined in the above recognition mode is compared with the teaching signal 6 which indicates the correct class of the input signals. If the comparison indicates that the response signal is wrong, the values of weighting factors of the element comparators 12 are changed to effect learning. More specifically, the LVQ2 selector 4 compares the class name of the response signal 5 as determined in the recognition mode with the correct class name given by the teaching signal 6. If the signals are not identical, the weighting factor correction process is performed. That is, the smallest value and the second smallest value are detected among the output values 10 of all intermediate nodes 3, and it is determined whether the following conditions are satisfied. If the following learning conditions are satisfied, the weighting factors of the element comparators 12 specified by the learning signal 7 via signal line 11 are changed according to expression (3) below.
The learning conditions are as follows. Ui is the intermediate node which provides the smallest output value Oi (determined to be the closest to the input pattern signal S), and Uj is the intermediate node which provides the second smallest output value Oj (determined to be the closest node to the input pattern signal S except for Oi). Ui and Uj belong to different classes Ci and Cj (Ci.noteq.Cj), respectively. S does not belong to the class Ci but belongs to the class Cj and falls within the window specified by the following expression: EQU Oj-Oi.ltoreq.th2 (2)
wherein th2 is a predetermined threshold constant.
The weighting factors in the intermediate nodes Ui and Uj are modified as follows: ##EQU2## wherein t is the time expressed in monotonically increasing integer (t=1, 2, . . . ); .alpha.(t) is a monotonically decreasing function having a sufficiently small value such as .alpha.(t)=1/(t+1).
The intermediate node Ui determined to be closest to the input pattern signal S is of a class which is different from the correct class, whereas the intermediate node Uj determined to be second closest to the input pattern signal S is of the correct class. The expression (2) implies that the input pattern signal S falls within the window area W of FIG. 4. The window W has a width of th2 around the border line between the neighboring templates encoded by the weighting factors of intermediate nodes Ui and Uj. These template vectors are depicted as circles 220a and 220b in FIG. 4a. If the input pattern signal vector 5 falls into this window area W, the input pattern lies in the border area of neighboring template vectors, and the input pattern signal cannot be distinguished correctly at a high rate.
In order to correct such a problem, the weighting factors of the intermediate node Ui are modified according to the modification set forth in the first part of expression (3). The modification of the weights separates the template represented by the weighting factors of the intermediate node Ui, having a class different from the input pattern signal S, in the vector space as shown by arrow ml in FIG. 4a. Likewise, the weighting factors of the intermediate node Uj are modified according to the second part of expression (3) so that the template represented by the weighting factors of the intermediate node Uj, having a class identical with that of the input pattern signal S, is adjusted in the direction of arrow m2 in FIG. 4a. The resulting adjusted weights resemble a pattern such as shown in FIG. 4b. Such learning activities are repeated until all of the weighting factors are organized to provide correct classification of the input pattern signal. The above learning mode is applied to all input pattern signals prepared for performing the learning operation and repeated until the weighting factor vector of the intermediate node no longer requires any correction according to expression (3). It is possible to accomplish this either in the learning mode alone or in the learning mode and the recognition mode in combination.
The pattern classification system using a neural network made by the LVQ2 learning technique is able to modify the weighting factors of an intermediate node so as to establish a recognition boundary between close classes in the pattern signal distribution. However, when an input pattern signal far apart from the template represented by the existing weighting factors is input, a wrong classification results and, the above window condition of expression (2) is not satisfied. Since the window condition is not satisfied, the learning activities of the above-described approach are impossible. In addition, where the classes Ci and Cj are determined to be the closest and second closest classes to the input pattern signal S and these classes are different from the correct class given by a teaching signal, the above-described approach fails. In particular, it does not provide correction of weighting factors of intermediate nodes. For this reason, the learning activities do not converge. Furthermore, when an input pattern signal of a class which has not yet been registered in the system is applied to the system as the input signal S, no learning takes place because there is no intermediate node of the proper class.
Accordingly, it is an object of the invention to provide a self-organizing pattern classification system which is able to learn from a wide variety of classes of input pattern signals.